package main

import "fmt"

//暴力解法:256ms 5%, 6.7MB 5%
func lengthOfLongestSubstring(s string) int {
	if len(s) < 2 {
		return len(s)
	}
	dp := make([]int, len(s))
	dp[0] = 1
	for i := 1; i < len(s); i++ {
		tmp := make(map[byte]bool)
		for j := i; j >= 0; j-- {
			if tmp[s[j]] {
				if dp[i-1] < i-j {
					dp[i] = i - j
				} else {
					dp[i] = dp[i-1]
				}
				break
			}
			tmp[s[j]] = true
			if j == 0 {
				dp[i] = i + 1
			}
		}
	}
	return dp[len(s)-1]
}

//动态规划:4ms 90%, 3.7MB 12%
func lengthOfLongestSubstring1(s string) int {
	if len(s) < 2 {
		return len(s)
	}
	dp := make([]int, len(s))
	dp[0] = 1
	tmp := map[byte]int{s[0]: 1}
	ans := 1
	for i := 1; i < len(s); i++ {
		if tmp[s[i]] > 0 {
			dp[i] = min(dp[i-1]+1, i+1-tmp[s[i]])
		} else {
			dp[i] = dp[i-1] + 1
		}
		if dp[i] > ans {
			ans = dp[i]
		}
		tmp[s[i]] = i + 1
	}
	return ans
}

func min(a, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}

//滑动窗口:8ms 67%,2.5MB 78%
func lengthOfLongestSubstring2(s string) int {
	tmp := map[byte]bool{}
	j, ans := -1, 0
	for i := 0; i < len(s); i++ {
		if i != 0 {
			tmp[s[i-1]] = false
		}
		for j+1 < len(s) && !tmp[s[j+1]] {
			tmp[s[j+1]] = true
			j++
		}
		ans = max(ans, j-i+1)
	}
	return ans
}

func max(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

func main() {
	fmt.Println(lengthOfLongestSubstring("au"))
	tmp := make(map[byte]int)
	fmt.Println(tmp['a'])
	fmt.Println(lengthOfLongestSubstring1("au"))
	fmt.Println(lengthOfLongestSubstring2("abcabcbb"))
}
